package dp;

import java.util.Arrays;

public class P377 {

    public int combinationSum4(int[] nums, int target) {
        int min = Arrays.stream(nums).min().getAsInt();
        int[] count = new int[]{0};
        backTrack(nums, min, target, count);
        return count[0];
    }

    void backTrack(int[] nums, int min, int left, int[] count) {
        if (left == 0 || min > left) {
            if (left == 0) {
                count[0] += 1;
            }
        } else {
            for (int num : nums) {
                if (left - num >= 0) {
                    backTrack(nums, min, left - num, count);
                }
            }
        }
    }

    public int dp(int[] nums, int target) {
        int[] dp = new int[target + 1];
        Arrays.sort(nums);
        for (int i = 1; i <= target; i++) {
            int total = 0;
            for (int num : nums) {
                if (num == i) {
                    total += 1;
                } else if (i - num >= 0) {
                    total += dp[i - num];
                } else {
                    break;
                }
            }
            dp[i] = total;
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        int target = 4;
        int result = new P377().dp(nums, target);
        System.out.println(result);
    }
}
